/*
	Copyright (c) 2009-2011, Stefan Webb.

	This file is part of SimpleML. Please read the file "license.txt", 
	which contains the conditions under which this software is distributed.
*/

/*!
	\file patriciatree.cpp
	\author Stefan Webb
	\brief Definition of PatriciaTree class methods.
*/

#include "stdafx.h"

/* Default constructor. */
PatriciaTree::PatriciaTree()
{
	// Call constructor with predetermined size 
	PatriciaTree(INITIAL_PTREE_SIZE);
}

/* Constructor with initial memory size. */
PatriciaTree::PatriciaTree(unsigned int size) : ContainsNodes(size)
{
}

/* Default destructor. */
PatriciaTree::~PatriciaTree()
{

}

/* Test membership of patricia tree. */
bool PatriciaTree::contains(const utf16* string)
{
	// Test for empty tree
	if (!nodes_.size())
		return 0;

	// Get best match for string
	utf16* match = bestMatch(string);

	// Compare best match to string
	return !wcscmp(string, match);
}

/* Given a string, will find best match in patricia tree. */
utf16* PatriciaTree::bestMatch(const utf16* string)
{
	// If there is only one string in tree then it must be best match
	if (nodes_.size() == 1 && !nodes_[0].child[1])
		return (utf16*) nodes_[0].child[0];

	// Walk tree for match...
	unsigned int i = 0, length = sizeString((utf16*) string);
	do {
		// Save node structure
		i >>= 1;

		// If differing byte is not outside string then fetch value
		unsigned char c = 0;
		if (indexByte(i) < length)
			c = ((char*)string)[indexByte(i)];

		// Calculate direction
		const int direction = (1 + (bitMask(i) | c)) >> 8;

		// Calculate next node indice
		i = nodes_[i].child[direction];

	// ...until we reach an external node
	} while(i & 1);

	return (utf16*) i;
}

/* Calculate the index byte for a given node. */
unsigned int PatriciaTree::indexByte(unsigned int i)
{
	return nodes_[i].indexByte & INDEXMASK;
}

/* Calculate the bit mask for a given node. */
unsigned int PatriciaTree::bitMask(unsigned int i)
{
	return (nodes_[i].indexByte & BITMASK) >> 24;
}

/* Insert string into patricia tree. No handover of memory ownership. */
bool PatriciaTree::insert(const utf16* string)
{
	// Handle inserting into empty tree
	if (!nodes_.size()) {
		// Check that string is aligned on 2-byte boundary
		if ((int)string & 1) {
			(error << L"String is not aligned on 2-byte boundary.").warning();
			return false;
		}

		// Create first internal node
		nodes_.addEmpty();
		nodes_[0].child[0] = (unsigned int) string;
		nodes_[0].child[1] = 0;

		// Return success
		return true;
	}

	// Get best match
	utf16* match;
	if (nodes_.size() == 1 && !nodes_[0].child[1]) {
		match = (utf16*) nodes_[0].child[0];
	}
	else
		match = bestMatch(string);

	// Find differing byte
	unsigned int i = 0, xor = 0;
	//unsigned char xor = 0;
	while (((char*)match)[i] == ((char*)string)[i]) {
		// If we get to end of string, then both must be equal
		if (i & 1) {
			if (!string[i >> 1] && !match[i >> 1])
				return false;
		}

		// Check out next character
		i++;
	}

	// Calculate XOR of first differing byte
	char diffByte = ((char*)match)[i];
	if (!string[i >> 1])
		xor = diffByte;
	else
		xor = ((char*)string)[i] ^ diffByte;

	// Find (least significant) differing bit
	while (xor & (xor - 1))
		xor &= xor - 1;
	// 1. Flip bits
	// 2. Find least significant bit
	// 3. Invert bits
	// 4. Flip bits
	//xor = ((xor * 0x0802LU & 0x22110LU) | (xor * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;
	//xor -= xor & (xor - 1);
	xor ^= 255;
	//xor = ((xor * 0x0802LU & 0x22110LU) | (xor * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;
	int direction = (1 + (xor | ((char*)string)[i])) >> 8;

	// Insert if second member
	// TODO: Check that i is not out of bounds (i.e. greater than 0xffffff). This is extremely unlikely!
	if (nodes_.size() == 1 && !nodes_[0].child[1]) {
		if (direction == 0)
			nodes_[0].child[1] = nodes_[0].child[0];
		nodes_[0].child[direction] = (unsigned int) string;
		nodes_[0].indexByte = (xor << 24) | i;
		return true;
	}

	// Create new node
	unsigned int j = nextFreeNode();

	// Find correct position to insert
	unsigned int k = 0, l = 0, length = sizeString((utf16*) string), newDirection;
	while (true) {
		// Save node structure
		k = l >> 1;

		// If differing byte is not outside string then fetch value
		unsigned char c = 0;
		if (indexByte(k) < length)
			c = ((char*)string)[indexByte(k)];

		// Calculate direction
		newDirection = (1 + (bitMask(k) | c)) >> 8;

		// Calculate next node indice
		l = nodes_[k].child[newDirection];

		// If the node is external then exit
		if (!(l & 1))
			break;

		// If the node is greater than this one then exit;
		if (indexByte(l >> 1) > i || (indexByte(l >> 1) == i && (char)bitMask(l >> 1) > (char)xor))
			break;
	}

	// Handle case of replacing root node
	// NOTE: I could combine the following two if's, but I'm not sure that
	// we are guaranteed that the k == 0 will be tested first.
	// Optimizing compiler should take care of code below anyway.
	if (k == 0) {
		// If root node is greater than current node then we need to handle differently
		if (indexByte(0) > i || (indexByte(0) == i && (char)bitMask(0) > (char)xor)) {
			// Swap nodes
			nodes_[j].child[0] = nodes_[0].child[0];
			nodes_[j].child[1] = nodes_[0].child[1];
			nodes_[j].indexByte = nodes_[0].indexByte;
			l = (j << 1) | 1;
			j = 0;
		}
		else
			nodes_[k].child[newDirection] = (j << 1) | 1;
	}
	else
		nodes_[k].child[newDirection] = (j << 1) | 1;

	// Create new links
	nodes_[j].child[direction] = (unsigned int) string;
	nodes_[j].child[1 - direction] = l;
	nodes_[j].indexByte = (xor << 24) | i;
	return true;
}

/* Remove string from patricia tree. */
bool PatriciaTree::remove(const utf16* string)
{
	// Return if there are no nodes
	if (!nodes_.size())
		return false;
	
	// If there is only one string in tree then it must be best match
	if (nodes_.size() == 1 && !nodes_[0].child[1]) {
		// If the string matches then delete the root node
		if (!wcscmp(string, (wchar_t*) nodes_[0].child[0])) {
			deleteNode(0);
			return true;
		}

		// Otherwise the string isn't in tree
		else
			return false;
	}

	// Otherwise walk tree for match...
	unsigned int i = 0, j = 0, length = sizeString((utf16*) string);
	int direction, lagDirection;
	while (true) {
		// If differing byte is not outside string then fetch value
		unsigned char c = 0;
		if (indexByte(i) < length)
			c = ((char*)string)[indexByte(i)];

		// Calculate direction
		direction = (1 + (bitMask(i) | c)) >> 8;

		// ...until we reach an external node
		if (!(nodes_[i].child[direction] & 1)) {
			// Check we have correct string
			if (!wcscmp(string, (wchar_t*) nodes_[i].child[direction]))
				break;
			else
				return false;
		}

		// Update indices
		lagDirection = direction;
		j = i;
		i = nodes_[j].child[direction] >> 1;
	}

	// Handle deleting root
	if (!i) {
		// If the other node is a string then no need to delete root
		j = nodes_[0].child[1 - direction];
		if (!(j & 1)) {
			if (direction == 0)
				nodes_[0].child[0] = nodes_[0].child[1];
			nodes_[0].child[1] = 0;
			return true;
		}

		// Otherwise we will need to delete root
		// TODO: Could make an assignment operator for node structure?
		j >>= 1;
		nodes_[0].child[0] = nodes_[j].child[0];
		nodes_[0].child[1] = nodes_[j].child[1];
		nodes_[0].indexByte = nodes_[j].indexByte;
		deleteNode(j);
		return true;
	}

	// Handle deleting non root node
	nodes_[j].child[lagDirection] = nodes_[i].child[1 - direction];
	deleteNode(i);
	
	return true;
}

/* Remove string at current cursor position. Update cursor. */
void PatriciaTree::remove()
{
	// If only two nodes in tree then handle this case.

	// Otherwise should go to successor or predecessor?
}

/* Empty entire patricia tree. */
void PatriciaTree::empty()
{
	nodes_.empty();
}

// TODO: Make HasCursor class ??

/* Allocates memory for cursor. Cursor only created when needed. */
void PatriciaTree::createCursor()
{
	cursor_.create(16);
}

/* Get first string in patricia tree. */
utf16* PatriciaTree::first()
{
	// Create cursor if needed
	createCursor();

	// Empty cursor
	cursor_.empty();

	// Navigate to leftmost (?) branch
	cursor_.push(1);
	return followBranch(0);
}

/* Get last string in patricia tree. */
utf16* PatriciaTree::last()
{
	// Create cursor if needed
	createCursor();

	// Empty cursor
	cursor_.empty();

	// Navigate to rightmost branch
	cursor_.push(1);
	return followBranch(1);
}

/* Follows either left or right branches until leaf, adding each node to cursor. */
utf16* PatriciaTree::followBranch(unsigned int direction)
{
	// Get cursor position
	unsigned int currentNode = cursor_.topElement();

	// Loop until reach external node
	// TODO: isExternal(i)/isInternal(i) private functions ??
	while(currentNode & 1) {
		// Store current node so we can backtrack later
		currentNode = nodes_[currentNode >> 1].child[direction];
		cursor_.push(currentNode);
	}

	return (utf16*) currentNode;
}

/* Get string at current cursor position. */
utf16* PatriciaTree::cursor()
{
	// We need to check that cursor is nonempty before we grab top element
	if(cursor_.size())
		return (utf16*) cursor_.topElement();
	else
		return 0;
}

/* Get next string in patricia tree. Update cursor. */
utf16* PatriciaTree::successor()
{
	return adjacent(1);
}

/* Get previous string in patricia tree. Update cursor. */
utf16* PatriciaTree::predecessor()
{
	return adjacent(0);
}

/* Helper function that gets adjacent element. */
utf16* PatriciaTree::adjacent(unsigned int direction)
{
	// Return first or last element if cursor is empty
	if (!cursor_.size())
		if (direction == 1)
			return first();
		else
			return last();

	// Keep going back until reach left or right child
	unsigned int currentNode, parentNode;
	do {
		// If no more elements then no successor exists
		if (cursor_.size() == 1) {
			// We have to preserve cursor
			followBranch(direction);
			return 0;
		}

		// Otherwise update node indices
		currentNode = cursor_.pop();
		parentNode = cursor_.topElement();
	} while (currentNode == nodes_[parentNode >> 1].child[direction]);
	
	// Handle when parent is root and no right node
	if (parentNode == 1 && !nodes_[0].child[direction])
		return 0;

	// Navigate to left or right most leaf of right or left child, depending
	cursor_.push(nodes_[parentNode >> 1].child[direction]);
	return followBranch(1 - direction);
}

// TODO: Function to set cursor to position that matches substring
// TODO: Function that gets next/previous string with substring
// Can replace the root as being the stop string in adjacent. Need new helper function.

/* Debug function */
void PatriciaTree::print()
{
	// Create cursor if needed
	createCursor();

	// Empty cursor
	cursor_.empty();

	// Initalize cursor
	unsigned int currentNode = 0;
	if (nodes_.size()) {
		if (nodes_[0].child[1])
			cursor_.push(nodes_[0].child[1]);
		cursor_.push(nodes_[0].child[0]);
	}

	console << nodes_.size() << " nodes in Patricia tree." << endl;

	// Depth first search taking left branches
	while(cursor_.size()) {
		// Get current node
		currentNode = cursor_.pop();

		// Handle internal node
		if (currentNode & 1) {
			currentNode >>= 1;
			cursor_.push(nodes_[currentNode].child[1]);
			cursor_.push(nodes_[currentNode].child[0]);
		}

		// Handle external node
		else
			console << (utf16*) currentNode << endl;
	}
}

/* Debug function */
void PatriciaTree::printNodes()
{
	for (unsigned int i = 0; i < nodes_.size(); i++) {
		console << L"Node " << i << L": ";
		if (nodes_[i].child[0] & 1)
			console << L"left = node " << (nodes_[i].child[0] >> 1) << L", ";
		else
			console << L"left = string '" << (utf16*) nodes_[i].child[0] << L"', ";
		if (nodes_[i].child[1]) {
			if (nodes_[i].child[1] & 1)
				console << L"right = node " << (nodes_[i].child[1] >> 1);
			else
				console << L"right = string '" << (utf16*) nodes_[i].child[1] << L"'";
		}
		console << endl;
	}
}